package leetcode.digui_huisu;

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 * <p>
 * 示例 2：
 * <p>
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 * <p>
 * 示例 3：
 * <p>
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * -104 <= xn <= 104
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/powx-n
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 解题思路:
 * x 0=1 x 1 * x1 = x 2
 * x4 =x2 * x2
 * x3 = x 1 * x1 *x
 * 也就是可以用递归 ,终止点 x 0 =1  然后x n 等于 x n/2 * x n/2  如果n 为奇数  还需要* x   当n为负数 为计算结果的1/n        当x为负数时不需要考虑
 * 时间复杂度分析 xn = x n/2 * x n/2  x n/2 = x n/4* x n/4  ....  x 2 = x 1  * x 1    x 1 = x 0  * x 0  反向看属于幂级别增长 所以为O(log n) 空间复杂度O(log 1)
 */
public class Solution50 {
    public double myPow(double x, int n) {
        return n < 0 ? 1 / calcPow(x, n) : calcPow(x, n);
    }

    private double calcPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double t = calcPow(x, n / 2);
//        if (n % 2 == 0) {
//            return t * t ;
//        }
//        return t * t* x;

        // 改进 考虑 n有为负数的情况 ,所以当n为负数情况 n % 2 >0 不成立, 此时有余数,但是余数是负数, 有余数我们期望是 再*x
        // 估如果是  n % 2 >0 来判断余数 当为负数时候 会被判定不存在余数  所以还是只能使用== 来判定有没有余数
        return n % 2 == 0 ? t * t : t * t * x;
    }

    public static void main(String[] args) {
        Solution50 solution50 = new Solution50();
        System.out.println(solution50.myPow(2.000000, -2));
    }
}
